Single number II

Time: O(N); Space: O(1); medium

Given an array of integers, every element appears three times except for one. Find that single one.

Example 1:

Input: nums = [1, 1, 1, 2, 2, 2, 3]

Output: 3

Notes:

• Your algorithm should have a linear runtime complexity.

• Could you implement it without using extra memory?

class Solution1(object):
    def singleNumber(self, nums) -> int:
        """
        :type nums: List[int]
        :rtype: int
        """
        one, two = 0, 0
        # print(~one, ~two)    # -1 -1
        for x in nums:
            # print(~x)   # ~1=-2; ~2=-3; ~3=-4
            one, two = (~x & one) | (x & ~one & ~two), \
                       (~x & two) | (x & one)
            # print(x, ':', one, two)
            # 1 : 1 0
            # 1 : 0 1
            # 1 : 0 0
            # 2 : 2 0
            # 2 : 0 2
            # 2 : 0 0
            # 3 : 3 0
        return one

s = Solution1()
nums = [1, 1, 1, 2, 2, 2, 3]
assert s.singleNumber(nums) == 3

# %%
class Solution2(object):
    def singleNumber(self, nums) -> int:
        """
        :type nums: List[int]
        :rtype: int
        """
        one, two, carry = 0, 0, 0
        for x in nums:
            two |= one & x
            one ^= x
            carry = one & two
            one &= ~carry
            two &= ~carry
            # print(one, two, three)
        return one

s = Solution2()
nums = [1, 1, 1, 2, 2, 2, 3]
assert s.singleNumber(nums) == 3

import collections

class Solution3(object):
    def singleNumber(self, nums) -> int:
        """
        :type nums: List[int]
        :rtype: int
        """
        # print(collections.Counter(list(set(nums)) * 3))   # Counter({1: 3, 2: 3, 3: 3})
        # print(collections.Counter(nums))                  # Counter({1: 3, 2: 3, 3: 1})
        return list((collections.Counter(list(set(nums)) * 3) - collections.Counter(nums)).keys())[0]

s = Solution3()
nums = [1, 1, 1, 2, 2, 2, 3]
assert s.singleNumber(nums) == 3

class Solution4(object):
    def singleNumber(self, nums) -> int:
        """
        :type nums: List[int]
        :rtype: int
        """
        # print(sum(set(nums)) * 3)  # 6 * 3 = 18
        # print(sum(nums))           # 12
        return (sum(set(nums)) * 3 - sum(nums)) // 2

s = Solution4()
nums = [1, 1, 1, 2, 2, 2, 3]
assert s.singleNumber(nums) == 3

class SolutionEX(object):
    def doubleNumber(self, nums) -> int:
        """
        :type nums: List[int]
        :rtype: int
        # Every element appears 4 times except for one with 2 times
        # Example 1:
        # Input: [1, 1, 1, 1, 2, 2, 2, 2, 3, 3]
        # Output: 3
        """
        one, two, three = 0, 0, 0
        # print(~one, ~two, ~three)    # -1 -1 -1
        for x in nums:
            # print(~x)   # ~1=-2; ~2=-3; ~3=-4
            one, two, three = (~x & one) | (x & ~one & ~two & ~three), \
                              (~x & two) | (x & one), \
                              (~x & three) | (x & two)
            # print(x, ':', one, two, three)
            # 1 : 1 0 0
            # 1 : 0 1 0
            # 1 : 0 0 1
            # 1 : 0 0 0
            # 2 : 2 0 0
            # 2 : 0 2 0
            # 2 : 0 0 2
            # 2 : 0 0 0
            # 3 : 3 0 0
            # 3 : 0 3 0
        return two

s = SolutionEX()
nums = [1, 1, 1, 1, 2, 2, 2, 2, 3, 3]
assert s.doubleNumber(nums) == 3

See also:

https://leetcode.com/problems/single-number-ii

https://www.lintcode.com/problem/single-number-ii